package lc;

import org.junit.Test;

public class Ex4 {
    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int m = nums1.length, n = nums2.length;
            if (m > n) return findMedianSortedArrays(nums2, nums1);
            int lo = 0, hi = m, len = m + n;
            int sm, lm, ll, lh, sl, sh;
            System.out.println("可以经过");
            while (lo <= hi) {
                //对短的进行遍历，对长的进行被动
                //长的具有转换空间，短的没有
                sm = (hi - lo) / 2 + lo;
                lm = (len + 1) / 2 - sm;
                System.out.println("sm:" + sm + "; lm:" + lm);
                sl = sm == 0 ? Integer.MIN_VALUE:nums1[sm - 1];
                sh = sm == m ? Integer.MAX_VALUE:nums1[sm];
                ll = lm == 0 ? Integer.MIN_VALUE:nums2[lm - 1]; 
                lh = lm == n ? Integer.MAX_VALUE:nums2[lm];
                if (sl <= lh && ll <= sh) {
                    return len % 2 == 0 ? (double)(sl + lh) / 2.0 : (double)(sl);
                } else if (sl > lh) {
                    hi = sm - 1;
                } else if (ll > sh) {
                    lo = sm + 1;
                }
            }
            return -1;
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums1 = new int[]{2,4};
        int[] nums2 = new int[]{1,3};
        System.out.println(s.findMedianSortedArrays(nums1, nums2));
    }
    
}
